Used as: Division One - Level Three:
Value | 1000 |
Submission Rate | 10 / 661 (1.51%) |
Success Rate | 4 / 10 (40.00%) |
High Score | Egor for 711.03 points (19 mins 53 secs) |
Average Score | 520.48 (for 4 correct submissions) |
There are some properties that are necessary and sufficient for a string B[i] to have minimal weight. There is a long explanation for them in the editorial for the division 2 version.
The string contains `min(26, L[i])` different letters.
All the positions of a letter are consecutive.
The final string is the concatenation of all the strings B[i] each of length L[i]. Each of those strings following the properties mentioned above. In order to calculate the weight of the final string we needed to know the left-most and right-most positions of each of its letters.
When a letter x is present in B[i], it will be present in a unique (for B[i]) sequence of consecutive positions. However, there are four different ways this letter will affect the final string.
Maybe B[i] is the only string that contains letter x.
Or maybe B[i] is the first but not the only string to contain x.
Or B[i] is the last (but not the only) string to contain x.
Or B[i] is a string that contains x and is neither the last or the first.
Of the `m = min(26, L[i])` letters that be present in B[i], we should decide four numbers: c, p, u and k such that:
`c + p + u + k = m` .
k letters appear only in B[i].
c letters appear for the last time (but not the only time) in B[i].
p letters appear for the first time (but not the only time) in B[i].
u letters appear in B[i] (Appeared before and will appear again).
Each of these letters makes B[i] contribute to the weight of the final string in a different way. Let s be the position in the final string of index 0 of B[i]. Let x be a letter used in B[i]:
If x is one the c letters, the right-most position of x is added to the weight. Weight increases by `s + R_x` (Where `R_x` is the right-most position of x in B[i].
If x is one of the p letters, the left-most position of x is subtracted from the weight. Weight is reduced by `s + L_x`.
If x is one of the k letters, then both the left-most position and right-most position of x in B[i] are used in the final weight. Final weight increases by `R_x - L_x`. Since all positions of x must be consecutive then this value is equal to the number of character positions used by x.
If x is one of the u letters, then something interesting happens: The weight for this letter is accounted in other parts of the final string, not B[i], so it doesn’t change the weight that B[i] contributes to the final string.
Let us say we make decisions for string B[i]. We pick four integers `(c,p,u,k)`. The values cannot be arbitrary. In order for us to use non-zero values for `p` or `u`, we must have started some letters in a previous string B[j] `(j < i)`. Let `o` be the number of letters that were added in a past string. We should have `c + u <= o`. Note that since the `c` letters are used for a last time in B[i] then we should not use them again, so o is reduced for later values of i. `p` and `k` mean that we have added letters that are completely new. So at first we have `(p + k <= 26)`, because there are 26 available letters in total. However, after we added these letters, we cannot make them start again in a later string. So this actually reduces the number of available letters.
The idea is then to define a function `f(a, o, i)` where:
i is the number of strings that we already processed. So we have already made decisions for `B[0], B[1], … B[i-1]`. We want to decide for `B[i]`, and find the minimum weight for all the following decisions.
a is the number of available new letters. Letters that were not added to the total string yet.
o is the number of open letters. Letters that were started in previous strings.
So the overall problem is solved by calling `f(26, 0, 0)`, there are 26 available letters, the current position is 0 and there are 0 letters that were started before.
The base case should be when `(i = |L|)`, in other words, we have already processed all of the strings. Every letter that was added to the final string should finish. This means that o must be 0. It is not necessary to use all the 26 available letters (Some final strings may only need a few letters, depending on the lengths of the fragments). So a can have any value. If o is not zero, the case is invalid. The minimum weight for an invalid case should be infinite, a very high number so that we know it is invalid.
Otherwise, we pick `(c,p,u,k)` for string B[i]. We need to follow some rules for this tuple. To recapitulate:
`c + p + u + k = m = min(26, L[i])`.
`c + u <= o`.
`p + k <= a`.
Imagine that we have somehow calculated the minimum weight `w` contributed by B[i] for the tuple `(c,p,u,k)`, what is the total weight to be returned by this decision?
The number of processed strings increases by 1: `i’ = i+1`.
The number of available letters is reduced by p and k: `a’ = a - p - k`.
The number of unfinished letters decreases by c but then increases again by p: `o’ = o - c + p`.
Therefore, the total cost for this `(c,p,u,k)` is `w + f(a - p - k, o - c + p, i + 1)`.
The result for `f(a,o,i)` should be just to find the tuple `(c,p,u,k)` that gives the minimum such result.
Note that since each of these values is `O(A)` (Where `A` is the size of the alphabet, in this case just 26), then there are `O(A^3)` valid tuples (Because of the first equation). The real number of valid tuples is much smaller, because of the other two conditions. And because `o + a <= A` (every time `o` is increased, `a` must be decreased). If we use dynamic programming, we can ensure that each parameter combination `(a,o,i)` is evaluated at most once. Assuming we need an algorithm of `O(1)` complexity to find the minimum weight contributed by tuple `(c,p,u,k)`, then the final complexity will be: `O(|L|*A^5)`. If we estimate it as 51*27^5 operations, it sounds very heavy. In reality, the actual number of tuples is small, and we can reduce the number of parameter combinations by using memoization. So let us try to calculate the weight of tuple `(c,p,u,k)` in O(1) and see what happens:
We want to calculate the weight contributed by a string B[i] of length L[i]. Its smallest index in the final string will be s. We have chose a tuple `(c,p,u,k)` for the number of each kind of letter included in B[i]. We also want to calculate this weight in `O(1)` time.
There is an analysis above in which we determined that the positions of the u and k letters do not matter. So we only care about the positions of c and p letters. Interestingly, the left-most positions of p letters contribute a negative number and the right-most positions of c letters contribute a positive number. How about we makes the c letters get the smallest possible positions and the p letters the largest possible?
We have determined the order of the letters. Another complication is the length of each group of equal letters. In the case of the c, p and k letters, the length should be as small as possible. In the case of u, the length does not matter, because u doesn’t contribute to the weight.
When `(u > 0)`, then we can make the lengths of the c, p and k letters exactly one. The u letters can fill the remaining space. If the lengths of the letters are 1, we can easily calculate the weight:
The k letters will each contribute 0 to the weight, because their length will be 1, so the right-most and left-most positions will be equal and the subtraction will be 0.
The c letters will use the c smallest positions in B[i], and this sum of positions is added to the weight:
`sum_(j=0)^(j<c)( s + j ) = c*s + sum_(j=0)^(j<c)(j) = c*s + (c*(c-1))/2`.
The p will use the p largest positions in B[i] and each of those positions is decreased from the weight:
`-sum_(j=0)^(j<p)( s + L[i] - 1 - j ) = -(s+L[i]-1)*p + ((p-1)*p) / 2`.
When `(u = 0)`, then we can no longer afford to make all strings have length 1. There is an additional `(L[i] - p - c - k)` length that has to be distributed between the groups of letters. The trick is to see that we should always try to make the left-most c letters and right-most p letters be the ones with length 1. As long as this happens the weight is optimal and the same. The proof is long and repetitive, so we will only include a few details.
Let the excess `(E = L[i] - p - c - k)` be distributed in three parts: `E = E_1 + E_2 + E_3`. `E_1` is the excess that is distributed between the c letters. `E_2` is distributed between the k letters and `E_3` between the p letters.
Each of the c letters will have a group of length equal to `(1 + e_i)`, where `(e_0 + e_2 + … + _ e_(c-1) = E_1)`. This changes their right-most positions to: `(s + e_0, s + 1 + e_0 + e_1, … s + c - 1 + e_0 + e_1 + … + e_(c-1))`. If we unwrap the sum like we did above, the total weight will be:
`c*s + (c*(c-1))/2 + ce_0 + (c-1)e_1 + … + e_(c-1)`
Each of the values `e_i`, except the last one is factored by a value higher than 1. It is possible to make all of the values of `e_i` equal to 0, except `e_(c-1)`. This would be optimal. So the optimal weight for `E_1` is:
`c*s + (c*(c-1))/2 + E_1`
Similarly, the optimal weight for p will be:
`-(s+L[i]-1)*p + ((p-1)*p) / 2 + E_3`
And the optimal weight for k will be `E_2`, the proof is similar to the proof at the beginning of the division 2 version.
The final weight will be:
`c*s + (c*(c-1))/2 + E_1 + E_2 -(s+L[i]-1)*p + ((p-1)*p) / 2 + E_3`
No matter how we assign each `E_i`, the excess cost is always `E_1 + E_2 + E_3 = E`.
The worst complexity appears to be high. `O(|L| * A^5)`, but the following c++ code actually takes less than 0.1 seconds to run in the worst case:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
static
const int INF = 1000000000;
int dp1[27][27][51];
vector < int > L;
int rec1(int a, int o, int i) // O( |L|* A^2 )
{
int & res = dp1[a][o][i];
if (res == -1) {
res = INF;
if (i == L.size()) {
if (o == 0) {
res = 0;
}
} else {
// starting index of the first letter in L[i]
// equal to the sum of all L[j] before L[i]:
int s = accumulate(L.begin(), L.begin() + i, 0); // O( |L|^2 * A^2 )
int m = std::min(L[i], 26); //must use m letters
//Letters that get closed in B[i]:
for (int c = 0; c <= o && c <= m; c++) { // O( |L|* A^3 )
// Letters that are opened in B[i]:
for (int p = 0; p + c <= m && p <= a; p++) { // O( |L|* A^4 )
//letters that are open (o) and will be reused inside B[i]:
for (int u = 0; p + c + u <= m && c + u <= o; u++) { // O( |L|* A^5 )
//letters that are new and used only inside B[i]:
int k = m - (p + c + u);
if (p + k > a) {
continue;
}
int w = rec1(a - p - k, o - c + p, i + 1);
if (u > 0) {
//Easy case when u > 0.
// * We can use 1-length groups for the k letters (0 weight)
// * We can keep the c letters to the left :
// added weight = sum of: (s, s+1, ... , s+c-1)
w += s * c + (c - 1) * c / 2;
// * We can keep the p letters to the right:
// reduced weight =
// sum of (s+L[i]-1-0, s+L[i]-1-1, ... s+L[i]-1-(p-1))
w -= (s + L[i] - 1) * p - (p - 1) * p / 2;
} else {
//Without the u "free" letters. We still want the
// c groups to be left-most, the p groups right-most
// The positions of k groups do not matter, only their
// length.
// In reality, we can show that the cost is always:
w += s * c + (c - 1) * c / 2;
w -= (s + L[i] - 1) * p - (p - 1) * p / 2;
w += (L[i] - c - p - k);
// No matter the lengths we pick.
}
res = std::min(w, res);
}
}
}
}
}
return res;
}
int getMinimum(vector < int > L) {
this - > L = L;
memset(dp1, -1, sizeof(dp1));
return rec1(26, 0, 0);
}
Taking a closer look: Once p and c were picked, it is always better to maximize u and minimize k. Larger values of u allow us to cut the additional weight. Smaller values of k reduce the number of used letters from a which will yield a better or equal result for the remaining strings. With this improvement, we can change the worst-case complexity to `O(|L|*A^4)`, which allows even the following iterative python solution to work under the time limit:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class StringWeight:
def getMinimum(self, L):
INF = 10 ** 9
# initialize a dp table:
dp = [[[INF] * (len(L) + 1) for i in range(0, 27)]
for j in range(0, 27)]
for a in xrange(0, 27):
# Base
case, i = L[i], then o must be 0:
dp[a][0][len(L)] = 0
for i in xrange(len(L) - 1, -1, -1): # O( | L | )
s = sum(L[j]
for j in range(0, i)) #O( | L | ^ 2)
# For each(a + o <= 26)
for a in xrange(0, 27): # O( | L | * A)
for o in xrange(0, (26 - a) + 1): # O( | L | * A ^ 2)
res = INF
#B[i] must contain m different letters:
m = min(L[i], 26)
# c letters will close in B[i]
for c in xrange(0, min(o, m) + 1): # O( | L | * A ^ 3)
# p letters will open in B[i]
for p in xrange(0, min(m - c, a) + 1): #O( | L | * A ^ 4)
# u letters are reused, only
try the maximum possible
# value of u which is:
u = min(m - c - p, o - c)
# k letters are new and are used only in B[i]:
k = m - (p + c + u)
if p + k <= a:
# recursive step:
w = dp[a - p - k][o - c + p][i + 1]
# add the cost
for the c letters:
w += s * c + (c - 1) * c / 2
# subtract cost thanks
for the p letters:
w -= (s + L[i] - 1) * p - (p - 1) * p / 2
if u == 0:
# The forced penalty
if there are no u letters:
w += L[i] - c - p - k
res = min(w, res)
dp[a][o][i] = res
return dp[26][0][0]